#ifndef HUFFMAN_H_INCLUDED
#define HUFFMAN_H_INCLUDED

#include <string>
#include <set>
#include "NodoHuffman.h"
#include <iostream>
#include "../commons/bitstream.h"
using namespace std;

template<class T> class Huffman {
private:
    std::multiset<NodoHuffman<T> > nodos;
    NodoHuffman<T>* raiz; //raiz del arbol huffman
    int cantelementos;
    std::string* codetable;

public:

    //constructor usado para obtener codigo prefijo, todos los elementos tienen frec 1
    Huffman(int numElementos) {
        cantelementos = 0;
        codetable = 0;
        for (int i=0; i<numElementos;i++) {
            NodoHuffman<int> nodo(i);
            agregarNodo(nodo);
        }
        armarArbol();
    }



    virtual ~Huffman() {
        delete[] codetable;
        borrarArbol();
    }

    void agregarNodo(NodoHuffman<T>& nodo) {
        nodos.insert(nodo);
        cantelementos++;
    }

    //armar el arbol de huffman, se almacena el nodo raiz
    void armarArbol() {
        typename std::multiset<NodoHuffman<T> >::iterator it;

        if (nodos.size() != 1) {
            while (nodos.size() > 1) {
                //saco los dos menores, los agrupo en un nodo y lo inserto
                it=nodos.begin();
                NodoHuffman<T>* nuevonodo = new NodoHuffman<T>();
                NodoHuffman<T>* primernodo = new NodoHuffman<T>(*it);
                nuevonodo->setIzq(primernodo);
                nodos.erase(it++);
                NodoHuffman<T>* segundonodo = new NodoHuffman<T>(*it);
                nuevonodo->setDer(segundonodo);
                nodos.erase(it);
                nuevonodo->setFrecuencia(primernodo->getFrecuencia()+segundonodo->getFrecuencia());
                nodos.insert(*nuevonodo);
            }
        }
        //me quedo un solo nodo en el set que es la raiz del arbol
        it=nodos.begin();
        NodoHuffman<T>* nuevaraiz = new NodoHuffman<T>(*it);
        raiz = nuevaraiz;

        getCodes();
    }

    //libera la memoria de los nodos del arbol
    void borrarArbol() {
        raiz->borrarHijos();
        delete raiz;
    }

    //llena la tabla con los codigos de cada caracter
    void getCodes() {
        codetable = new std::string[cantelementos];
        std::string code;
        if (raiz->esHoja())
            codetable[0] = "0";
        else
            getCodesRec(code, raiz->getIzq(), raiz->getDer());

    }

    //recorre el arbol y llena los valores de la tabla de codigos
    void getCodesRec(std::string code,NodoHuffman<T>*& nodo1,NodoHuffman<T>*& nodo2) {
        std::string iz= code+"0";
        std::string de= code+"1";

        if (nodo1->esHoja()) {
            T valor= nodo1->getValor();
            codetable[valor] = iz;
        }
        else {
            getCodesRec(iz,nodo1->getIzq(),nodo1->getDer());
        }

        if (nodo2->esHoja()) {
            T valor = nodo2->getValor();
            codetable[valor] = de;
        }
        else {
            getCodesRec(de,nodo2->getIzq(),nodo2->getDer());
        }
    }

    std::string getCodeFor(T caracter) {
        return (codetable[caracter]);
    }

    void imprimirtabla() {
        for(int i = 0; i<cantelementos;i++) {
            cout << codetable[i] << endl;
        }
    }

    void encode(BitStream*& stream,T val) {
        std::string codigo = this->getCodeFor(val);
        std::string::iterator it;
        for ( it = codigo.begin() ; it < codigo.end(); it++) {
            if (*it == 48)
                stream->putBit(false);
            if (*it == 49)
                stream->putBit(true);
        }
    }

    T decode(BitStream*& stream) {
        bool fin = raiz->esHoja();
        if(raiz->esHoja()){
        	stream->getBit();
        }
        NodoHuffman<T>* actual = raiz;
        while (!fin) {
            bool bit = stream->getBit();
            if (bit)
                actual = actual->getDer();
            if (!bit)
                actual = actual->getIzq();
            fin = actual->esHoja();
        }
        return actual->getValor();
    }
};

#endif // HUFFMAN_H_INCLUDED
